package com.leetcode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No287
 * @description
 * @date 2021/3/6 下午7:34
 */
public class No287 {
    public static void main(String[] args) {

    }

    // 二分法
    public static int findDuplicate(int[] nums) {
        int len = nums.length;
        int left = 1,right = len - 1;
        while (left < right){
            int mid = left + (right - left) >> 1;
            int cnt = 0;
            for(int num:nums){
                if(num <= mid){
                    cnt++;
                }
                if(cnt > mid){
                    right = mid;
                }else {
                    left = mid + 1;
                }

            }
        }
        return left;



    }

}
